package leetcode.sort;

/**
 * 快排
 */
public class QSort {

    public static int[] qsort(int[] nums, int head, int tail) {
        //如果子序列只有一个值则直接返回
        if (head >= tail) {
            return nums;
        }

        //将第一个值设定为比较值
        int key = nums[head];

        int left = head;
        int right = tail;

        while (left < right) {
            //比key大的放在左边
            while (nums[left] > key && left < right) {
                left++;
            }

            //比key小的放右边
            while (nums[right] < key && left < right) {
                right--;
            }

            if (left < right) {
                int temp = nums[right];
                nums[right] = nums[left];
                nums[left] = temp;
            }
        }
        nums[left] = nums[left];
        nums[left] = key;
        qsort(nums, head, left - 1);
        qsort(nums, left + 1, tail);

        return nums;
    }


}
